package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _662_MaximumWidthofBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        int length = 0;
        if(root==null) return length;
        List<TreeNode> nodes = new ArrayList<>();
        List<Integer> pos = new ArrayList<>();
        nodes.add(root);
        pos.add(1);
        while (!nodes.isEmpty()) {
            List<TreeNode> q = new ArrayList<>();
            List<Integer> tp = new ArrayList<>();
            length = Math.max(length, (pos.get(pos.size() - 1) - pos.get(0)) + 1);
            for (int i = 0; i < nodes.size(); i++) {
                TreeNode node = nodes.get(i);
                if (node.left != null) {
                    q.add(node.left);
                    tp.add(pos.get(i) * 2);
                }
                if (node.right != null) {
                    q.add(node.right);
                    tp.add(pos.get(i) * 2 + 1);
                }
            }
            nodes = q;
            pos = tp;
        }
        return length;
    }
}
